package main.Q901_1000;

import java.util.ArrayList;
import java.util.List;

public class Q931_940 {
    public static void main(String[] args) {
        System.out.println("Question931：下降路径最小和");
        System.out.println("Question932：");
        System.out.println("Question933：最近的请求次数");
        System.out.println("Question934：最短的桥");
        System.out.println("Question935：");
        System.out.println("Question936：");
        System.out.println("Question937：");
        System.out.println("Question938：");
        System.out.println("Question939：");
        System.out.println("Question940：");
    }
}

class Question931 {
    public int minFallingPathSum(int[][] matrix) {
        int length = matrix.length, min = Integer.MAX_VALUE;
        int[][] dp = new int[length][length];
        for (int i = length - 1; i >= 0; i--) {
            for (int j = 0; j < length; j++) {
                if (i == length - 1) {//最后一行
                    dp[i][j] = matrix[i][j];
                    continue;
                }
                int left = Integer.MAX_VALUE, mid = dp[i + 1][j], right = Integer.MAX_VALUE;
                if (j - 1 >= 0) left = dp[i + 1][j - 1];
                if (j + 1 < length) right = dp[i + 1][j + 1];
                dp[i][j] = Math.min(left, Math.min(mid, right)) + matrix[i][j];//最小值选取
            }
        }
        for (int i = 0; i < length; i++) min = Math.min(min, dp[0][i]);
        return min;
    }
}

class Question933 {
    List<Integer> list;

    public Question933() {
        list = new ArrayList<>();
    }

    public int ping(int t) {
        list.add(t);
        int lowIndex = 0, lowVal = t - 3000, left = 0, right = list.size() - 1;
        while (left < right) {
            int midIndex = left + (right - left) / 2, midVal = list.get(midIndex);
            if (midVal < lowVal) {
                left = midIndex + 1;
            } else {
                right = midIndex;
            }
        }

        return list.size() - left;
    }
}

class Question934 {
    public void process(int[][] grid, int r, int c, List<int[]> list) {
        list.add(new int[]{r, c});
        int n = grid.length;
        grid[r][c] = 2;
        if (r - 1 >= 0 && grid[r - 1][c] == 1) process(grid, r - 1, c, list);
        if (r + 1 < n && grid[r + 1][c] == 1) process(grid, r + 1, c, list);
        if (c - 1 >= 0 && grid[r][c - 1] == 1) process(grid, r, c - 1, list);
        if (c + 1 < n && grid[r][c + 1] == 1) process(grid, r, c + 1, list);
    }

    public boolean process1(int[][] grid, int r, int c, List<int[]> list) {
        int n = grid.length;
        if (r - 1 >= 0 && grid[r - 1][c] == 0) {
            grid[r - 1][c] = 2;
            list.add(new int[]{r - 1, c});
        } else if (r - 1 >= 0 && grid[r - 1][c] == 1) return true;//扩展到另一个岛屿
        if (r + 1 < n && grid[r + 1][c] == 0) {
            grid[r + 1][c] = 2;
            list.add(new int[]{r + 1, c});
        } else if (r + 1 < n && grid[r + 1][c] == 1) return true;
        if (c - 1 >= 0 && grid[r][c - 1] == 0) {
            grid[r][c - 1] = 2;
            list.add(new int[]{r, c - 1});
        } else if (c - 1 >= 0 && grid[r][c - 1] == 1) return true;
        if (c + 1 < n && grid[r][c + 1] == 0) {
            grid[r][c + 1] = 2;
            list.add(new int[]{r, c + 1});
        } else if (c + 1 < n && grid[r][c + 1] == 1) return true;
        return false;
    }

    public int shortestBridge(int[][] grid) {
        int count = 0, n = grid.length;
        List<int[]> island1 = new ArrayList<>(), newIsland = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            boolean flag = false;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    process(grid, i, j, island1);//岛屿1
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        newIsland = island1;
        boolean flag = false;
        while (true) {
            List<int[]> tempIsland = new ArrayList<>();
            for (int[] island : newIsland) {
                if (process1(grid, island[0], island[1], tempIsland)) {
                    flag = true;
                    break;
                }
            }
            count++;
            newIsland = tempIsland;
            if (flag) break;
        }
        return count - 1;
    }
}

class Question938 {
    int total = 0;

    public void process(TreeNode root, int low, int high) {
        if (root == null) return;
        if (root.val <= high && root.val >= low) total += root.val;
        process(root.left,low,high);
        process(root.right,low,high);
    }

    public int rangeSumBST(TreeNode root, int low, int high) {
        process(root, low, high);
        return total;
    }
}